/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-11-07
 * Time: 20:40
 */
class ListNode{
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
public class Day15 {
    //142.环形链表II
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }

        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
            if (fast == low){
                fast = head;
                while (fast != low){
                    fast = fast.next;
                    low = low.next;
                }
                return fast;
            }
        }
        return null;
    }
    //876.链表中间节点
    public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
        }
        return low;
    }
    //JZI.22 链表中倒数第k个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode low = head;
        while (k != 0){
            fast = fast.next;
            k--;
        }
        while (fast != null){
            fast = fast.next;
            low = low.next;
        }
        return low;
    }
    //JZII.27 回文链表
    public boolean isPalindrome(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode newHead = head;
        ListNode cur = head;
        ListNode curNext = null;
        ListNode fast = head;
        ListNode low = head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
            curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        cur = newHead;
        if (fast != null && fast.next == null){
            low = low.next;
        }
        while (low != null && cur != null){
            if (low.val != cur.val){
                return false;
            }
            low = low.next;
            cur = cur.next;
        }
        return true;
    }

    //MS.02.04
    public ListNode partition(ListNode head, int x) {
        if (head == null){
            return null;
        }
        ListNode underxs = null;
        ListNode underxe = null;
        ListNode upxs = null;
        ListNode upxe = null;

        ListNode cur = head;
        while (cur != null){
            if (cur.val < x){
                if (underxs == null){
                    underxs = cur;
                    underxe = cur;
                }else{
                    underxe.next = cur;
                    underxe = cur;
                }
            }else{
                if (upxs == null){
                    upxs = cur;
                    upxe = cur;
                }else{
                    upxe.next = cur;
                    upxe = cur;
                }
            }
            cur = cur.next;
        }
        if (upxe != null){
            upxe.next = null;
        }
        if (underxe != null) {
            underxe.next = upxs;
        }else{
            return upxs;
        }
        return underxs;
    }
}
